It is well known to send and receive multicast data traffic over an Internet Protocol (IP) network. The following documents, all incorporated by reference herein in their entireties, discuss IP: J. Postel, RFC 0791, “Internet Protocol,” September 1981; J. Postel, RFC 0792, “Internet Control Message Protocol,” September 1981; J. Postel, RFC 0768, “User Datagram Protocol,” September 1981; F. Baker, Ed., RFC 1812, “Requirements for IP Version 4 Routers,” June 1995, all published by the Internet Society of Reston, Va., and all available on the world wide web. It is further well known for hosts, e.g., computers on a network, to report their membership in a group of hosts that receives a particular multicast, i.e., a group of destinations for a particular set of multicast data packets. For example, management of multicast groups according to the Internet Group Management Protocol (IGMP) is discussed in S. E. Deering, RFC 988, “Host Extensions for IP Multicasting,” July 1986; S. E. Deering, RFC 1054, “Host Extensions for IP Multicasting,” May 1988; W. Fenner, RFC 2236, “Internet Group Management Protocol, Version 2,” November 1997; B. Cain et al., RFC 3376, “Internet Group Management Protocol, Version 3,” October 2002; all published by the Internet Society of Reston, Va., all available on the world wide web, and all incorporated herein by reference in their entireties.
Under the known IP multicast forwarding model, multicast traffic is essentially forwarded along a tree that is rooted at the traffic source. Each recipient of the multicast traffic (i.e., each group member) is at a leaf of the tree, and multicast routers at the vertices. According to the known IP multicast forwarding model, forwarding decisions for each packet are made independently at each multicast router, based upon the source of the packet and its destination group. For example, varieties of Protocol Independent Multicast (PIM), known to those skilled in the art, use a multicast topology table referred to herein as the Multicast Routing Information Base (MRIB) to populate routing tables stored in routers. Each router in the network uses the MRIB to determine next-hop routers. A data packet may be sent to more than one router. Duplicate elimination is performed at each multicast router by only accepting incoming packets arriving on the expected incoming edge of the tree (rather than, for example, according to a sequence number assigned to the incoming packet). In most multicast routing protocols, including PIM, the forwarding tree is usually a reverse shortest-path tree (e.g., it contains the shortest path from each member of the group that receives the multicast back to the multicast source), although, as is known, PIM may deviate slightly from this shortest-path model when needed to resolve parallel entry points to a single multi-access network.
Table 1 shows an exemplary, simplified version of an IP multicast forwarding table for a multicast router in a network using PIM.
TABLE 1Forwarding InformationIndicesOutgoingOutgoingOutgoingOutgoingDestinationIncomingInterfaceInterfaceInterface InterfaceSource SGroup GInterface eth0eth1eth2eth3128.89.17.1 225.0.0.1Eth0OffOnOnOn128.89.17.1 227.9.9.2Eth0OffOnOffOff128.89.13.1225.0.17.29 Eth0OffOnOffOn114.27.14.2226.7.7.9Eth1OnOffOnOnTable 1 is indexed by source S and destination group G, and assumes that the router has four interfaces. Each entry specifies the incoming interface from which to accept packets from a source S; packets arriving over any other interface from that source S are ignored as probable duplicates. Further, each entry specifies, for each possible outgoing interface, whether packets from a source S to a particular destination G are to be forwarded via that outgoing interface.
Note that Table 1 does not control or even specify which routers or hosts on the outgoing interface(s) are to receive the forwarded packet. That is, decisions regarding whether to accept an incoming packet, and how to forward it, are based upon a table indexed by packet source S and destination group G. Thus, Table 1, for example, specifies, for each source S and group G, the incoming interface from which to accept the packet, and the outgoing interfaces onto which to forward the packet. Because these forwarding decisions depend upon the packet source S as well as destination group G, multicast forwarding is very different from unicast forwarding, which depends upon a packet's destination alone.
As just discussed, an important peculiarity of the IP multicast forwarding model is that forwarding decisions are actually based upon network interfaces, not next-hop or previous-hop routers. The decision as to whether to accept a multicast packet is based upon the interface through which the packet arrives, not the previous-hop router. Likewise, a multicast forwarding table actually specifies the outgoing interfaces through which to forward the packet, not the next hop routers. The multicast forwarding model implicitly assumes that the multicast packet is then available for reception at every router and host connected to the network attached to that interface, so that the decision whether or not to accept the packet is actually made by the recipient. This model is well-matched to wired broadcast networks such as Ethernets, where the cost of delivering a packet to every router and host on a particular network is no higher than the cost of delivering it to just one. However, the existing multicast forwarding model is poorly adapted to other kinds of networks where the cost of delivering a packet to multiple recipients is significantly higher than the cost of delivering the packet to just one recipient alone. This is especially true for multi-hop networks having high costs associated with delivering data packets, such as radio networks, acoustic networks, etc., that provide minimal bandwidth, uncertain reliability, and transmission delays.
PIM, mentioned above, is a known approach for routing data to multi-cast groups in, or spanning, networks, such as wide-area networks (WANs). The designation “Protocol Independent” refers to PIM's ability to co-exist with a wide variety of Internet Protocol (IP) unicast routing protocols. Known variants of PIM include at least a “sparse mode” (SM) version, PIM-SM, and a “dense mode” (DM) version, PIM-DM. PIM-SM has been described in D. Estrin et. al., RFC 2362, “Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification,” June 1998, published by the Internet Society of Reston, Va. and available on the world wide web, fully incorporated by reference herein in its entirety. PIM-DM has been described in Steven Deering et al, “Protocol Independent Multicast Version 2, Dense Mode Specification, Draft 5” May 1997, distributed as an Internet Draft by the Network Working Group of the Internet Engineering Task Force (IETF) organized by the Internet Society of Reston, Va., also fully incorporated by reference herein in its entirety. The present disclosure includes references to both PIM-SM and PIM-DM, and, in cases where a reference to both PIM-SM and PIM-DM is intended, will refer simply to “PIM.” Inasmuch as PIM is well known and understood in the art, it is not necessary to provide herein details regarding every aspect of PIM. However, certain aspects of PIM relevant to this disclosure are discussed briefly below for the purpose of providing background and context to the present disclosure.
According to PIM-SM, the MRIB (i.e., the multicast topology table mentioned above) is established and maintained by means of what are known as JOIN/PRUNE messages, and used for the routing of multicast traffic. PIM-SM is a pro-active protocol, meaning that potential recipients must explicitly join a group through use of JOIN/PRUNE messages before it can receive any data for that group, and must explicitly leave the group to cease receiving data. A network using PIM-SM will have at least one specially configured router referred to as a rendezvous point (RP). An RP serves as the root of a distribution tree for a group of multicast receivers (i.e., a group of recipients of multicast traffic) in cases in which the distribution tree is not specific to any one source of multicast traffic. A single PIM-SM router per network acts as a designated router (DR) on behalf of all hosts (i.e., receivers of multicast data) that are connected to that network, e.g., a local area network (LAN). For each group for which it has active members, a DR periodically sends JOIN/PRUNE messages to the RP. The purpose of JOIN/PRUNE messages is simple. Regarding Joins, a prerequisite to receiving traffic directed toward a particular group is joining the group. Regarding Prunes, once a multicast has ended, or the host is no longer interested in receiving it, the host wishes to be removed from the group.
PIM-DM, unlike PIM-SM, is a reactive protocol. That is, all potential recipients by default receive multicast traffic for all groups. Recipients that do not wish to receive this data may suppress it by sending JOIN/PRUNE messages. PIM-DM thus differs from PIM-SM in two ways. First, PIM-DM does not need, and does not define, rendezvous points. Second, PIM-DM does not automatically transmit JOIN/PRUNE messages on a periodic basis, which instead must be explicitly triggered. PIM-DM is by design most applicable when the number of sources per group is small, and almost every potential recipient belongs to almost every group. Table 2 provides an overview of considerations relevant to determining when each of PIM-SM and or PIM-DM can and/or should be used for a particular application.
TABLE 2ConsiderationPIM-DMPIM-SMLarge number of multicastNO (PRUNE scaling)YESsources per groupLow data rate per sourceNO (PRUNE overhead mayYESexceed user traffic)Bursty sourceNO (PRUNE ineffective due to YES, as long as thresholds forpropagation delay)switching to source-based treesare adjusted so that traffic burstsdo not create topologicaloscillationsLocalized group membershipNO (PRUNE overhead isYESinflicted on entire networkuniverse)Small number of sources eachYESYESwith high uniform data rate, withgroup members widely dispersedRapidly changing groupYESYESmembershipsAvoid single point-of-failureYESPARTIAL (new rendezvous-pointvulnerabilitiesmust be elected if previous RPfails)
Although PIM, by its very name, is supposed to be protocol independent, it actually is designed for routing over multiple single-hop networks such as Ethernets and point-to-point wired links. When employed over multiple large, low-bandwidth, multi-hop networks, PIM as presently known suffers from a number of deficiencies, and would function very poorly. Certain of these deficiencies are discussed in turn below.
Lack of Support for Layered Networks
PIM as presently known lacks support for layered network structures. Like most IP multicast routing protocols, PIM forwards multicast traffic according to a determination of a network interface, not according to a determination of a “next hop” router. PIM implicitly assumes that multicast traffic forwarded onto a particular network will be delivered non-selectively to every router on that network, regardless of whether or not that router actually has any downstream group members to which that traffic is to be delivered. Stated another way, PIM as presently known assumes that every multicast router is implicitly a member of every multicast group for which traffic has been injected onto the networks to which the router is attached.
The known PIM model is appropriate for an Ethernet, but not for a multi-hop, low bandwidth network such as some wireless networks. On an Ethernet, the bandwidth consumed by multicasting a packet to every node on the network is no different from the bandwidth consumed by unicasting it to a single node or multicasting it to selected nodes. Consequently, no efficiency is lost if every multicast router simply puts its Ethernet interface into “promiscuous multicast” mode, meaning that it is to receive all multicast traffic.
On a multi-hop, low-bandwidth network, however, there are significant costs to be borne if every multicast router is to receive all multicast traffic. For example, certain possibilities for reusing router space can only be exploited if distribution of multicast traffic within the low-bandwidth network can be limited to the necessary recipients. If all routers with downstream group members are geographically localized, it is highly wasteful to deliver multicast traffic for that group to other, remote routers that do not need the information. Accordingly, “promiscuous multicast” mode can have a significant effect on bandwidth consumption in the low-bandwidth network having a large number of small, localized groups.
Scaling of Hello Messages to Large Networks
As is known, each PIM router generates a HELLO message that must be multicast (broadcast) to every other router on a network. Even with net wide broadcast implemented through a minimal connected cover of broadcast relays, the bandwidth consumed by these HELLO messages at a minimum increases linearly with the number of routers on the network. Furthermore, when every router on a network is also a PIM router, most of the HELLO messages are wasted; the set of PIM neighbors is identical to the set of unicast routing neighbors, and can be determined from this set.
Graph 100 shown in FIG. 1 plots bandwidth consumption caused by HELLO messages as the number of routers in a network increases. The bandwidth capacity of a typical network is shown by line 110 superimposed on the graph 100. The bandwidth consumed by PIM HELLO messages is shown by a line 120. As can be seen, the bandwidth consumed by HELLO messages on a network with a total capacity of only about 2 megabytes per second, such as a radio network, is problematic when the network grows to even a few hundred nodes. As a rough rule of thumb, it is generally desirable that network routing overhead from all sources and layers combined not exceed ten percent of the total network capacity. The overhead from PIM HELLO messages alone from each layer would approach this ten percent limit in a radio node network with one or two thousand nodes. Particularly in a layered network environment, the combined HELLO overhead from all layers would clearly be prohibitive.
As discussed above, the bandwidth consumed by PRUNE/JOIN messages is independent of the number of routers on a network. However, the load from HELLO messages grows with the number of routers on a network and presently imposes severe limits on the scalability of radio networks.
Scaling of Assert Messages to Large Networks
On a multi-hop low bandwidth network, where the unicast cost may be different for each pair of routers, the usual PIM reverse-shortest-path rule, known to those skilled in the art, will not necessarily select a single entry point for each multicast source as it would on a standard Ethernet on which the unicast cost is essentially the same for each pair of routers. However, routers configured according to PIM as presently known will nevertheless attempt to enforce a single entry point, which would be elected through an exchange of ASSERT messages.
Graph 200 shown in FIG. 2 plots bandwidth consumption caused by ASSERT messages as the number of routers in a network increases. The bandwidth capacity of a typical network is shown by line 210 superimposed on the graph 200. The bandwidth consumed by PIM ASSERT messages is shown by line 220. As can be seen, the bandwidth consumed by ASSERT messages on a network with a total capacity of only about 2 megabytes per second, such as a radio network, is problematic when the network grows to even a few hundred nodes. In particular, enforcement of a single entry point by means of ASSERT messages poses several difficulties.
First, enforcement of a single entry point does not necessarily lead to routes for user multicast traffic that are optimal or close to optimal, particularly when the exit points are sparse and distant from each other.
Moreover, as illustrated by FIG. 2, ASSERT messages themselves do not scale well to large networks. The bandwidth consumed by ASSERT messages for PIM-DM is proportional to the product of the number of groups, times the number of sources per group, times the number of distinct entry points per source computed by the reverse-shortest-path algorithm. This relationship may be expressed as follows:Bandwidth=(NGroups)(NSrcs/Group)(NEntryRtrs/Src).For PIM-SM, the above relationship differs only in that the number of sources is replaced by the number of distribution trees (1 for the RP tree+1 for each source rooted tree):Bandwidth=(NGroups)(NTrees/Group)(NEntryRtrs/Src).Thus, ASSERT messages scale more poorly than JOIN/PRUNE messages discussed above by an additional factor proportional to the number of distinct entry points per source, i.e., NEntryRtrs/Group/Src. As shown in FIG. 2, the bandwidth consumed by such ASSERT messages can be significant. Consequently, the bandwidth load from ASSERT messages can severely limit the scalability of a radio network to large numbers of groups and sources.
Further, when transit delays are large, or completion rates are low, the ASSERT mechanism for electing a preferred entry point becomes ineffective at suppressing unneeded user traffic. Entry points losing the election will continue to inject duplicate user traffic until such time as they receive an ASSERT from the winner of the election.
Scaling of Bootstrap and CANDIDATE_RP_ADVERTISEMENT Messages
PIM-SM as presently known elects rendezvous points through exchange of communication messages such as BOOTSTRAP and CANDIDATE_RP_ADVERTISEMENT messages, which are known and understood by those skilled in the art. The bandwidth consumed by the bootstrap procedure of PIM-SM is proportional to the product of the number of groups and the number of candidate rendezvous points per group. This relationship may be expressed as follows:Bandwidth=(NGroups)(Ncandidate-RPs/Group).
For maximum robustness in the face of possible partitioning of a routing domain (including failure or destruction of routers), every group member in the routing domain would have to be a candidate rendezvous point. In such a case, the bandwidth consumed by the bootstrap procedure would be proportional to the product of the number of groups times the number of members per group in the entire routing domain. This relationship may be expressed as follows:Bandwidth=(NGroups)(NMembers/Group).Note that the number of members in the routing domain may be much larger than the number of exit points from the low bandwidth network itself.
Consequently, the bootstrap mechanism of PIM-SM limits scalability to large numbers of group members—unless, of course, one is willing to accept a lower degree of robustness.